`:top

`!Configuration graphs`! are a theoretical tool used in `F33f`_`[computational complexity theory`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Computational_complexity_theory]`_`f to prove a relation between `F33f`_`[graph`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Graph_(discrete_mathematics)]`_`f `F33f`_`[reachability`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Reachability]`_`f and `F33f`_`[complexity classes`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Computational_complexity_theory]`_`f.

>>Contents

• `F0af`_`[Definition`#definition]`_`f

• `F0af`_`[Useful property`#useful-property]`_`f

• `F0af`_`[Size of the graph`#size-of-the-graph]`_`f

• `F0af`_`[Use of this object`#use-of-this-object]`_`f

• `F0af`_`[References`#references]`_`f

• `F0af`_`[Bibliography`#bibliography]`_`f

-─

>>Definition

A theoretical computational model, like `F33f`_`[Turing machine`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Turing_machine]`_`f or `F33f`_`[finite automata`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Finite_automata]`_`f, explains how to do a computation. The model explains both what is an initial configuration of the machine and which steps can be taken to continue the computation, until we eventually stop. A `*configuration`*, also called an `*instantaneous description`* (`*ID`*), is a finite representation of the machine at a given time. For example, for a finite automata and a given input, the configuration will be the current state and the number of read letters, for a Turing machine it will be the state, the content of the tape and the position of the head. A configuration graph is a directed `F33f`_`[labeled graph`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Labeled_graph]`_`f where the label of the vertices are the possible configurations of the models and where there is an edge from one configuration to another if it corresponds to a computational step of the model.

The initial and accepting configuration(s) of the machine are special vertices of the configuration graph. The computation accepts if and only if there is a path from an initial vertex to an accepting vertex.

>>Useful property

If there exists exactly one initial state, then a computation is deterministic if and only if from any configuration there is at most one possible step, so if and only if the graph is of out-degree 1.

Once a dummy initial vertex with an edge to every initial vertex and a dummy accepting vertex with an edge from every accepting vertex are added, checking if there is an accepting computation only requires to check if there is a path from the initial vertex to the accepting vertex, which is the `F33f`_`[reachability`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Reachability]`_`f problem.

A computation is said to be unambiguous if there exists at most one path from an initial vertex to an accepting vertex.

A cycle in the graph corresponds to an infinite loop in the computation.

>>Size of the graph

The computational graph can be of infinite size if there are no restrictions on possible configurations; indeed, it is easy to see that there are Turing machines which can reach arbitrarily large configurations.

It is also possible to have finite graphs: on `F33f`_`[Deterministic finite automaton`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Deterministic_finite_automaton]`_`f with s {\\displaystyle s} states, for a given word of size n {\\displaystyle n} the configuration is composed of the position of the head and the current state. So the graph is of size ( n + 1 ) s {\\displaystyle (n+1)s} , and the accessible part from the initial state is of size n + 1 {\\displaystyle n+1} .

>>Use of this object

This notion is useful because it reduces computational problems to graph `F33f`_`[reachability`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Reachability]`_`f problems.

For example, since reachability is in `F33f`_`[NL`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=NL_(complexity)]`_`f when we can represent configurations in space which is logarithmic in the size of the input, and since the configuration of a Turing Machine in `F33f`_`[NL`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=NL_(complexity_class)]`_`f is indeed of logarithmic size, it follows that graph-reachability is `F33f`_`[complete`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Complete_(complexity)]`_`f for NL.`:cite-ref-papa-1-0[`F5bf`_`[1`#cite-note-papa-1]`_`f]

In the other direction, it helps to verify the complexity of a computation model; the decision problem for a (deterministic) model whose configurations are of space which is logarithmic in the size of the input is in (`F33f`_`[L`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=L_(complexity)]`_`f) `F33f`_`[NL`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=NL_(complexity)]`_`f. This is for example the case of finite automata and finite automata with one counter.

>>References

`:cite-note-papa-1`!1.`! `F0af`_`[↑`#cite-ref-papa-1-0]`_`f `F33f`_`[Papadimitriou, Christos H.`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Christos_Papadimitriou]`_`f (1994). `*Computational Complexity`*, Reading, Massachusetts: Addison-Wesley. `F33f`_`[ISBN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISBN_(identifier)]`_`f 0-201-53082-1.

>>Bibliography

• `:citerefarorabarak2009`a`F33f`_`[Arora, Sanjeev`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Sanjeev_Arora]`_`f; Barak, Boaz (2009). `*Computational complexity, a modern approach`*. `F33f`_`[Cambridge University Press`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Cambridge_University_Press]`_`f. `F33f`_`[ISBN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISBN_(identifier)]`_`f 978-0-521-42426-4. Section 4.3: NL-completeness, p. 87.

`c`F0af`_`[↑ Back to top`#top]`_`f`a